package ACwing.P2DataSturcture;

import java.io.*;

/**
 * @Date : 2023-03-07
 * @Description:154.滑动窗口 单调队列
 */
public class MonotonicQueue {

    // hh 表示队头，tt表示队尾的后一个位置
    static int N=1000010;
    static int[] a=new int[N],q=new int[N];
    public static void main(String[] args) throws IOException {
        StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        sc.nextToken();
        int n = (int)sc.nval;
        sc.nextToken();
        int k = (int)sc.nval;
        for (int i = 0; i < n; i++) {
            sc.nextToken();
            a[i]=(int)sc.nval;
        }
        int hh=0,tt=-1;//单调队列队头和队尾
        for (int i = 0; i < n; i++) {
            if(hh<=tt&&q[hh]<i-k+1)hh++;//  已经输入了k个数，且队头不在队列中
            while(hh<=tt&&a[q[tt]]>=a[i]) tt--;//不满足单调的时候，不加入队列
            q[++tt]=i;// 入队
                //输入最小值
            if(i>=k-1) wt.print(a[q[hh]]+" ");//出队
        }
        wt.println();
        hh=0;tt=-1;//重置队列
        for (int i = 0; i < n; i++) {
            if(hh<=tt&&q[hh]<i-k+1)hh++;//  已经输入了k个数，且队头不在队列中
            while(hh<=tt&&a[q[tt]]<=a[i]) tt--;//不满足单调的时候，不加入队列
            q[++tt]=i;// 入队
                //输出最大值
            if(i>=k-1) wt.print(a[q[hh]]+" ");//出队
        }
        wt.println();
        wt.flush();
    }
}
